1. Field of the Invention
This invention relates generally to antenna arrays and, more particularly, to beam-forming systems for such arrays. Even more particularly, the invention relates to a digital beam former capable of generating multiple output beams from an array of antenna elements. Applications for the invention include surveillance radar, instantaneous automatic direction finding, and adaptive arrays.
2. Description of the Prior Art
Techniques for performing a discrete cyclic convolution of two sequences of numbers are known. A definition for such a convolution is as follows: ##EQU1## If computed directly, this convolution requires N.sup.2 multiplications for two input sequences x and h, each of a length N. However, as is well known to those skilled in the art of digital signal processing, there exist arithmetic transforms having the cyclic convolution property, i.e., the transform of the cyclic convolution of two sequences is equal to the product of their transforms. Thus, if the two sequences x and h are transformed by a transform having the cyclic convolution property into two new sequences, it is necessary only to find the linear vector product of the transformed sequences (which requires only N multiplications) to produce the transform of the desired result. When this result is processed through an inverse transform operation, the final result is the desired output sequence, in this case y.
The most well known of such transforms is the Fast Fourier Transform (FFT) which is an algorithm for computing the discrete Fourier transform (DFT) of a sequence. Another such transform found useful in digital convolution is the Fermat Number Transform (FNT). The FNT and its application to digital signal processing are described, for example, in "Fast Convolution Using Fermat Number Transforms with Applications to Digital Filtering" by R. C. Agarwal and C. S. Burrus, IEEE Transforms on Acoustics, Speech, and Signal Processing, April, 1974, pages 87-97.
The discrete Fourier transform F(k) of a sequence x(n) may be defined as ##EQU2##
In contrast, the Fermat Number Transform F(k) of a sequence x(n) may be defined as ##EQU3## Equations (2) and (3) apply to sequences of length N, where N is an integral power of 2. In equation (3), F.sub.t is a Fermat number, defined as F.sub.t =2.sup.b +1, b=2.sup.t ; and .alpha. is the Nth root of 1 (mod F.sub.t), as will be discussed in greater detail below.
It is seen that the FNT resembles the DFT with .alpha. replacing exp(-2.pi.j/N), and with all arithmetic performed modulo a Fermat number.
The significance of the FNT to digital signal processing lies in the fact that if .alpha. is an integral power of 2, multiplications by powers of .alpha. are accomplished by merely rotating bits in a register. In addition, the FFT algorithm may be used to compute the FNT as long as the length of the sequences is a power of two. Thus, the FNT can be implemented using only adders and bit shifters, with the only multiplications necessary being the linear vector product of the two transforms. The FFT algorithm is discussed, for example, in "What is the Fast Fourier Transform?" by W. T. Cochran et al, IEEE Transactions on Audio and Electroacoustics, June, 1967, at pages 45-55.
It is also quite common to design specialized hardware to perform Fermat arithmetic. Many such designs are based on novel digital coding schemes for the representation of numbers, such as described, for example, in "Hardware Realization of a Fermat Number Transform" by J. H. McClellan, IEEE Transactions on Acoustics, Speech & Signal Processing, June, 1976, pages 216-225, and in "Modified Circuits for Fermat Transform Implementation" by H. Nussbaumer, IBM Technical Disclosure Bulletin, October, 1976, pages 1720-1.
Electrical networks for forming multiple beams from linear antenna arrays have also been described in the literature. See, for example, "Multiple Beams from Linear Arrays," J. R. Shelton, IRE Transactions on Antennas and Propagation, March, 1961, which describes the well known Butler matrix which forms multiple beams by utilizing passive analog networks of couplers and phase shifters.
Digital beam forming techniques using the FFT are also known. The Butler matrix is a hardwired analog FFT that produces, at its n output spigots, n antenna beams that are mutually orthogonal sinc functions; one for each of the n antenna elements. The difficulties of analog computation are preserved when hardware realization of a Butler matrix is attempted, thus many systems use the FFT to form antenna beams. In either case, the antenna beams generated have definite drawbacks unless some amplitude weighting function is applied to the antenna element outputs, and even such an adjustment avails little in beam improvement.
The FFT may be regarded conceptually as producing the cross-correlation of the antenna array and a circular function whose angular progression from point to point is related to the angle of arrival of the beam being formed. Since such a cross-correlation is a constant function of its variable, each output "spigot" represents this cross-correlation evaluated at a single point, and each "spigot" or output coefficient is due to a different angle of arrival, therefore due to a different (special) frequency circular function. Although the low quality beam patterns generated by the FFT can be used in linear combination (since they form a basis) to produce any realizable beam pattern or set of beam patterns, an additional computation load is thus generated whenever beam sharpening is required.